import java.util.*;
import java.lang.*;

public class Postfix
{
	private final int NUMBER = 30;
	
	private final int PLUS = 60;
	private final int MINUS = 60;
	private final int TIMES = 90;
	
	private final int LEFTPAR = 121;
	private final int RIGHTPAR = 122;
	
	public<E> String iterableToString(Iterable<E> x)
	{
		Iterator<E> it = x.iterator();
		
		String res = new String();
		while(it.hasNext())
		{
			res += (it.next().toString() + " ");
			
			it.remove();
		}
		
		return res;
	}
	
	class stackIterable<E> implements Iterable<E>
	{
		private Iterator it = null;
		
		stackIterable(Iterator<E> it)
		{
			this.it = it;
		}
		
		public Iterator<E> iterator()
		{
			return it;
		}
	}
	
	boolean isDigit(char bit)
	{
		if ((bit >= '0') && (bit <= '9'))
		{
			return true;
		}
		
		return false;
	}
	
	boolean isOperator(String bit)
	{
		if (bit.equals("*") || bit.equals("-") || bit.equals("+"))
		{
			return true;
		}
		
		return false;
	}
	
	int bitType(char bit)
	{
		int type = -1;
		
		switch(bit)
		{
			case '+':
			{
				type = PLUS;
				
				break;
			}
			case '-':
			{
				type = MINUS;
				
				break;
			}
			case '*':
			{
				type = TIMES;
				
				break;
			}
			default:
			{
				type = -1;
				
				break;
			}
		}
		
		if (isDigit(bit) == true)
		{
			type = NUMBER;
		}
		
		if (bit == '(')
		{
			type = LEFTPAR;
		}
		else if (bit == ')')
		{
			type = RIGHTPAR;
		}
		
		if (type < 0)
		{
			throw new RuntimeException();
		}
		
		return type;
	}
	
	String infixToPostfix(String infixExpr)
	{
		String res = new String();
		LinkedStack<Character> stack = new LinkedStack<Character>();
		
		char charArray[] = infixExpr.toCharArray();
		
		for (int i = 0; i < charArray.length; i++)
		{
			String bit = Character.toString(charArray[i]);
			
			if ((isDigit(charArray[i]) == false) && (isOperator(bit) == false) 
					&& (bit.equals("(") == false) && (bit.equals(")") == false))
			{
				throw new RuntimeException();
			}
			
			int type = bitType(charArray[i]);
			
			switch (type)
			{
				case NUMBER:
				{
					res += Character.toString(charArray[i]);
					
					break;
				}
				case LEFTPAR:
				{
					stack.push(charArray[i]);
					
					break;
				}
				case RIGHTPAR:
				{
					while(stack.empty() == false)
					{
						if (bitType((Character)stack.top()) != LEFTPAR)
						{
							char operator = (Character)stack.pop();
							
							res += Character.toString(operator);
						}
						else
						{
							stack.pop();
						}
					}
					
					break;
				}
				default:
				{
					while(stack.empty() == false)
					{
						char operator = (Character)stack.top();
						if (isOperator(Integer.toString(operator)) == false)
						{
							break;
						}
						
						int operatorType = bitType(operator);
						
						if (operatorType > type)
						{
							break;
						}
						
						stack.pop();
						
						res += Integer.toString(operator);
					}
					
					stack.push(charArray[i]);
					
				}
			}
		}
		
		while (stack.empty() == false)
		{
			char operator = stack.pop();
			
			//System.out.println(res);
			//System.out.println(operator);
			
			res += Character.toString(operator);
		}
		
		return res;
	}
	
	public int evaluatePostfix(String postfixExpr)
	{
    	LinkedStack<Integer> stack = new LinkedStack<Integer>();
    	
    	char charArray[] = postfixExpr.toCharArray();
    	for (int i = 0; i < charArray.length; i++)
    	{
    		String bit = Character.toString(charArray[i]);
    		
    		if ((isDigit(charArray[i]) == false) && (isOperator(bit) == false))
    		{
    			throw new RuntimeException();
    		}
    		
    		switch(charArray[i])
    		{
    			case '*':
    			{
    				if (stack.empty())
    				{
    					throw new RuntimeException();
    				}
    				
    				int exp1 = stack.pop();
    				
    				if (stack.empty())
    				{
    					throw new RuntimeException();
    				}
    				
    				int exp2 = stack.pop();
    				
    				stack.push(exp1 * exp2);
    				
    				break;
    			}
    			case '+':
    			{
    				if (stack.empty())
    				{
    					throw new RuntimeException();
    				}
    				
    				int exp1 = stack.pop();
    				
    				if (stack.empty())
    				{
    					throw new RuntimeException();
    				}
    				
    				int exp2 = stack.pop();
    				
    				stack.push(exp1 + exp2);
    				
    				break;
    			}
    			case '-':
    			{
    				if (stack.empty())
    				{
    					throw new RuntimeException();
    				}
    				
    				int exp1 = stack.pop();
    				
    				if (stack.empty())
    				{
    					throw new RuntimeException();
    				}
    				
    				int exp2 = stack.pop();
    				
    				stack.push(exp2 - exp1);
    				
    				break;
    			}
    			default:
    			{
    				stack.push(Integer.parseInt(bit));
    			}
    		}
    		
    		//System.out.println(iterableToString(new stackIterable<Integer>(stack.iterator())));
    	}
		
		if (stack.empty())
		{
			throw new RuntimeException();
		}
		
		int res = stack.pop();
		
		if (!stack.empty())
		{
			throw new RuntimeException();
		}
		
		return res;
	}
	
	public static void main(String args[])
	{
		Postfix ps = new Postfix();
		
		//System.out.println(ps.evaluatePostfix("6534+*+"));
		
		System.out.println(ps.infixToPostfix("(2*(8+3))+(2*4)"));
		
	}
}
